10889. Потерянный подарок
Стэн шокирован, так как потерял
часть подарка Оли. Драгоценным
подарком были две коробки, наполненные хрустальными шариками. Шарики в одной
коробке были красными, а в другой черными. Когда Оли дарил подарок, он произнес
следующие слова с шаловливой улыбкой: “Стэн! Если ты смешаешь шарики из двух
коробок и наугад выберешь два, то вероятность того что они будут одного цвета
равна ½.”. Стэн весело вернулся домой с двумя коробками, но тут
неожиданно уронил на пол коробку с черными шариками, которые раскатились по
полу. Стэн бросился собирать, и в результате смог собрать не меньше 70% черных
шариков. По количеству красных шариков и собранных черных Вам следует
определить количество потерянных черных шариков.
Вход. Каждая
строка содержит два натуральных числа r – количество красных шариков и b – количество черных шариков,
найденных Стэном. Последняя строка содержит два ноля и не обрабатывается.
Выход. Для каждого теста в отдельной
строке вывести ответ. Если количество красных шариков r не соответствует выше описанной истории, то вывести “No.
of red balls invalid”. Если количество красных шариков верно, но количество найденных черных шариков не
корректно, то вывести строку “No. of black balls invalid”. Если оба числа r и b корректны, то вывести одно или
два целых числа в одной строке. Эти числа указывают на возможное количество
потерянных черных шариков. Выводимые числа следует разделять одним пробелом и
отсортировать по возрастанию.
Пример входа
10 5
11 1
0 0
Пример выхода
1
No. of red balls invalid
РЕШЕНИЕ
вероятность
Анализ алгоритма
Пусть Оли подарил Стэну bb черных шариков (из которых b он потом нашел). Тогда из фразы Оли, сказанной
при вручении подарка следует, что
Упрощая выражение, получим
квадратное уравнение:
Поскольку r известно, решаем его относительно bb. Для этого перепишем уравнение в
виде
Дискриминант равен 
= 1 + 8r.
Корни уравнения: 
.
Отсюда заключаем, что:
·
Если 1 + 8r не является полным квадратом, то количество красных
шариков не корректно.
·
Если
оба корня
bb1 и bb2 не целые, то количество красных шариков не
корректно.
·
Для
того чтобы количество
черных шариков было корректным, необходимо чтобы корень bb удовлетворял двум соотношениям:
1. b ≤ bb (количество
найденных черных шариков b должно быть не больше количества подаренных bb).
2. 0.7bb ≤ b (количество
найденных черных шариков b не меньше 70% их общего количества).
Если оба значения r и b являются корректными, то следует
вывести только неотрицательные найденные
значения bb.
Реализация алгоритма
Пусть bres – один
из удвоенных корней уравнения . Если он не делится нацело на 2, то количество красных
шариков некорректно, в таком случае возвращаем -1. В случае некорректности значения b возвращаем -2.
// -
1 red invalid
// -
2 black invalid
int check(int
bres)
{
if (bres % 2)
return -1; bres /= 2;
if (!((0.7 *
bres <= b) && ((b <= bres)))) return
-2;
return bres -
b;
}
Основная часть программы.
while(scanf("%d
%d",&r,&b),r + b)
{
Вычисляем дискриминант d квадратного
уравнения. Если он не является полным квадратом, то количество красных шариков
не корректно.
d = 1 + 8 * r; dd = sqrt(1.0 * d + 1e-7);
if (dd * dd
!= d) printf("No. of red balls invalid\n");
else
{
Вычисляем корни квадратного уравнения res1 и res2. Выводим
результат в зависимости от их значения.
res1 = check(1 + 2*r - dd);
res2 = check(1 + 2*r + dd);
if ((res1
== -1) && (res2 == -1)) printf("No. of
red balls invalid\n");
else if ((res1 == -2) && (res2 == -2))
printf("No.
of black balls invalid\n");
else
{
if ((res1
>= 0) && (res2 >= 0)) printf("%d
%d\n",res1,res2); else
if (res1
>= 0) printf("%d\n",res1); else printf("%d\n",res2);
}
}
}